/**
 * @author LKQ
 * @date 2022/2/26 16:22
 * @description 数学，排列组合 用count[x]统计x出现的个数，x+y+z = target
 * 则 1. x，y,z各不同时，那么有 count[x] * count[y] * count[z] 种情况
 *   2. x == y != z 时，那么有 count[x] * (count[x]-1) / 2 * count[z]
 *   3. x != y == z 时，那么有 count[x] * (count[y] * count[y-1] / 2;
 *   4. x == y == z时，那么从count[x]中选择3中不同的下标 有 Cn3 = n!/ (n-3)!/3!
 */
public class FormalSolution {
    public static void main(String[] args) {

    }
    public int threeSumMulti(int[] A, int target) {
        int MOD = 1_000_000_007;
        long[] count = new long[101];
        for (int x: A) {
            count[x]++;
        }
        long ans = 0;

        // All different
        for (int x = 0; x <= 100; ++x) {
            for (int y = x+1; y <= 100; ++y) {
                int z = target - x - y;
                if (y < z && z <= 100) {
                    ans += count[x] * count[y] * count[z];
                    ans %= MOD;
                }
            }
        }

        // x == y != z
        for (int x = 0; x <= 100; ++x) {
            int z = target - 2*x;
            if (x < z && z <= 100) {
                ans += count[x] * (count[x] - 1) / 2 * count[z];
                ans %= MOD;
            }
        }

        // x != y == z
        for (int x = 0; x <= 100; ++x) {
            if (target % 2 == x % 2) {
                int y = (target - x) / 2;
                if (x < y && y <= 100) {
                    ans += count[x] * count[y] * (count[y] - 1) / 2;
                    ans %= MOD;
                }
            }
        }

        // x == y == z
        if (target % 3 == 0) {
            int x = target / 3;
            if (0 <= x && x <= 100) {
                ans += count[x] * (count[x] - 1) * (count[x] - 2) / 6;
                ans %= MOD;
            }
        }

        return (int) ans;
    }
}
